/*

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
*/
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
void dfs(map<char,string> & ketpad,
         int pos, string & digits, string & element, vector<string> & rst){
    if (pos == digits.size()) {
        rst.emplace_back(element);
        return;
    }
    char x = digits[pos];
    string s = ketpad[x];
    for (int i = 0; i < s.size(); ++i) {
        element.push_back(s[i]);
        dfs(ketpad, pos + 1, digits, element, rst);
        element.pop_back();
    }
}

vector<string> letterCombinations(string digits)
{
    vector<string> rst;
    if ( digits.length() == 0) {
        return rst;
    }
    map<char,string> keypad;
    keypad['2'] = "abc";
    keypad['3'] = "def";
    keypad['4'] = "ghi";
    keypad['5'] = "jkl";
    keypad['6'] = "mno";
    keypad['7'] = "pqrs";
    keypad['8'] = "tuv";
    keypad['9'] = "wxyz";
    
    rst.clear();
    string element;
    dfs(keypad, 0, digits, element, rst);
    return rst;
}


int main(int argc, const char * argv[])
{
    letterCombinations("23");
    return 0;
}
